/*
Date:				2017-2-07
Author:				GangTimes
Address:			JSB-0210-220
dependent file:   	iterator.h head.h

The file is a kind of implemation with linked list.
*/

#ifndef LIST_H_
#define LIST_H_

template<typename T>
class Node
{
public:
	T data;
	Node* pre;
	Node* next;

	Node(T d, Node* p = nullptr, Node* n = nullptr)
		:data(d), pre(p), next(n){}
};

template<typename T>
class list;

//inherit the iterator
// 再vs中不需要从新引入类型名称（继承即可）  在gcc中需要重新引入类型名称
template<typename T>
struct list_iterator :public iterator<bidirectional_iterator_tag, T, ptrdiff_t, Node<T>*,T&>
{

	typedef Node<T>									node_type;
	typedef list_iterator<T> 						iterator;
	typedef typename iterator::pointer 				pointer;
	typedef typename iterator::iterator_category 	iterator_category;
	typedef typename iterator::value_type 			value_type;
	typedef typename iterator::difference_type 		difference_type;
	typedef typename iterator::reference 			reference;
	pointer node;
	list_iterator(pointer x = nullptr) :node(x){}
	list_iterator(const iterator & x) :node(x.node){}
	
	reference operator *()const
	{
		return node->data;
	}

	bool operator !=(const iterator & x)
	{
		return node != x.node;
	}

	iterator& operator++()
	{
		node = (pointer)(node->next);
		return *this;
	}
	
	iterator& operator--()
	{
		node = (pointer)(node->pre);
		return *this;
	}
	
	iterator& operator++(int)
	{
		iterator tmp = *this;
		++(*this);
		return tmp;
	}

	iterator& operator--(int)
	{
		iterator tmp = (*this);
		--(*this);
		return tmp;
	}
	
	pointer operator->()const
	{
		return node;
	}
};

template<typename T>
class list
{
public:
	typedef typename list_iterator<T>::value_type				value_type;
	typedef typename list_iterator<T>::reference				reference;
	typedef typename list_iterator<T>::pointer					pointer;
	typedef typename list_iterator<T>::difference_type			difference_type;
	typedef typename list_iterator<T>::iterator					iterator;
	typedef Node<T>												node_type;
private:
	pointer head;
	pointer rear;
	int count;

public:
	list(pointer h = nullptr, pointer r = nullptr)
		:head(h), rear(r),count(0){}
	
	list(int num,T d=0) :list()
	{
		for (int i = 0; i < num; ++i)
		{
			push_back(d);
			++count;
		}
	}
	
	list(const list & l) :list()
	{
		for (auto temp = l.begin(); temp != l.end(); ++temp)
		{
			push_back(*temp);
			++count;
		}
	}
	
	list(iterator first, iterator last) :list()
	{
		for (auto temp = first; temp != last; ++temp)
		{
			push_back(*temp);
			++count;
		}
	}
	
	~list()
	{
		clear();
	}

	void pop_back()
	{
		if (head == rear)
		{
			delete head;
			rear = nullptr;
			head = nullptr;
			--count;
			return;
		}
		
		if (head == nullptr && rear == nullptr)
		{
			cout << "there is not any more element" << endl;
			return ;
		}
		
		rear = rear->pre;
		free(rear->next);
		rear->next = nullptr;
		--count;
	}
	
	void pop_front()
	{
		if (head == rear)
		{
			delete head;
			rear = nullptr;
			head = nullptr;
			--count;
			return;
		}
		
		if (head == nullptr && rear == nullptr)
		{
			cout << "there is not any more element" << endl;
			return;
		}
		
		head = head->next;
		free(head->pre);
		head->pre = nullptr;
		--count;
	}

	void clear()
	{
		while (head!=rear)
		{
			pop_front();
		}
		
		delete head;
		head = nullptr;
		rear = nullptr;
		count = 0;
	}
	void erase(iterator index)
	{
		pointer pre_node = index.node->pre;
		pointer next_node = index.node->next;

		pre_node->next = next_node;
		next_node->pre = pre_node;

		delete index.node;
		index.node = nullptr;
		--count;
	}
	
	void erase(iterator first, iterator last)
	{
		for (auto temp = first; temp != last;++temp)
		{
			earse(temp);
		}
	}
	
	void assign(iterator first, iterator last)
	{
		auto index=head;
		
		for (auto temp = first; temp != last; ++temp)
		{
			if (index == nullptr)
			{
				push_back(*temp);
				index = rear->next;
			}		
			
			else
			{
				index->data = (*temp);
				index=index->next;
			}
		}
		
		if(index!=nullptr)
		{
			while (index != rear)
			{
				pop_back();
			}
			
			auto pre_node = index->pre;
			pre_node->next = nullptr;
			rear = pre_node;
			delete index;
			index = nullptr;
			--count;
		}
		
	}
	void assign(int num, T d)
	{
		auto index = head;
		
		for (auto temp = 0; temp < num; ++temp)
		{
			if (index == nullptr)
			{
				push_back(d);
				index = rear->next;
			}
			
			else
			{
				index->data = d;
				index = index->next;
			}
		}
		
		if (index != nullptr)
		{
			while (index != rear)
			{
				pop_back();
			}
			
			auto pre_node = index->pre;
			pre_node->next = nullptr;
			rear = pre_node;
			delete index;
			index = nullptr;
			--count;
		}
	}

	void insert(iterator index, T d)
	{
		Node<T>* node = new Node<T>(d);

		auto node_pre = index.node->pre;
		auto node_curr = index.node;
		
		node->pre = node_pre;
		node->next = node_curr;
		node_pre->next = node;
		node_curr->pre = node;
		++count;
	}
	void insert(iterator index, int num, T d)
	{
		for (int i = 0; i < num; ++i)
		{
			insert(index, d);
		}
	}

	void insert(iterator index, iterator first, iterator last)
	{
		for (auto temp = first; temp != last; ++temp)
		{
			insert(index,*temp);
		}
	}

	void merge(list<T> & l)
	{
		for (auto temp = l.begin(); temp != l.end(); ++temp)
		{
			push_back(*temp);
			++count;
		}
		l.clear();
	}
	
	reference back()
	{
		return rear->data;
	}
	
	reference front()
	{
		return head->data;
	}
	
	void push_back(T elem)
	{
		if (head == nullptr)
		{
			head = new Node<T>(elem);
			rear = head;
			++count;
			return;
		}
		
		pointer temp = new Node<T>(elem);
		temp->pre = rear;
		rear->next = temp;
		rear = temp;
		++count;
	}
	
	void push_front(T elem)
	{
		if (head == nullptr)
		{
			head = new Node<T>(elem);
			rear = head;
			++count;
			return;
		}
		
		pointer temp = new Node<T>(elem);
		temp->next = head;
		head->pre = temp;
		head = temp;
		++count;
	}
	
	void remove(T elem)
	{
		for (auto temp = head; temp != rear->next;)
		{
			if ((temp->data) == elem)
			{
				temp = temp->next;
				erase(iterator(temp->pre));
			}
			
			else
			{
				temp = temp->next;
			}
		}
	}
	
	iterator begin()
	{
		return iterator(head);
	}
	
	iterator end()
	{
		return iterator(rear->next);
	}
	
	iterator begin()const
	{
		return iterator(head);
	}
	
	iterator end()const 
	{
		return iterator(rear->next);
	}
	
	iterator rbegin()
	{
		return iterator(rear);
	}
	
	iterator rend()
	{
		return iterator(head->next);
	}
	
	bool isempty()
	{
		return (rear == head) && (head == nullptr);
	}
	
	void show()
	{
		for (auto temp = begin(); temp != end();++temp )
		{
			cout << *temp << endl;
		}
	}
	
	int size()
	{
		return count;
	}
};
#endif